package com.xy6.algo.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * 
 * <pre>
 * 时间复杂度：O(n^2)，空间复杂度：n+1
 * 
 * 遍历集合元素（从首到尾），当前索引i
 * 遍历集合元素（从首到尾），当前索引j
 * 比较i、j两个元素大小，如果elem[i]>elem[j]，则交换两个元素。否则，不处理
 * 遍历结束后，数组元素已按从小到大排列
 * </pre>
 * 
 * @author frank
 * @since 2017-06-02
 */
public class SortBubble {

	/**
	 * 输出结果：
	 * 
	 * 1: 1 3 2 2: 1 2 3
	 */
	public static void main(String[] args) {
		int[] arr = new int[] { 3, 1, 2 };
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}

	/**
	 * 冒泡排序
	 * 
	 * @param arr
	 */
	public static void sort(int[] arr) {
		int size = arr.length;
		int temp = 0;
		for (int i = 0; i < size; i++) {
			for (int j = i; j < size; j++) {
				if (arr[i] > arr[j]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}

}
